//
//  16.合并两个排序的链表.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/18.
//

import Foundation
/*
 题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
 思路：先判断输⼊的链表是否为空的指针。如果第⼀个链表为空，则直接返回第⼆个链表；如果第⼆个链表为空，则直接返回第⼀个链表。如果两个链表都是 空链表，合并的结果是得到⼀个空链表。 两个链表都是排序好的，我们只需要从头遍历链表，判断当前指针，哪个链表中的值⼩，即赋给合并链表指针即可。使⽤递归就可以轻松实现。下面用循环实现
 */
func offer_16() {
    let node1 = Solution.ListNode(val: 1)
    let node2 = Solution.ListNode(val: 2)
    let node3 = Solution.ListNode(val: 3)
    let node4 = Solution.ListNode(val: 4)
    let node5 = Solution.ListNode(val: 5)
    let node6 = Solution.ListNode(val: 6)
    node1.next = node3
    node3.next = node5
    node2.next = node4
    node4.next = node6
    var node = Solution().merge(node1, node2)
    while node != nil {
        print(node!.val)
        node = node?.next
    }
}

fileprivate class Solution {
    class ListNode {
        var val: Int
        var next: ListNode?
        init(val: Int) {
            self.val = val
        }
    }
    
    func merge(_ pHead1: ListNode?, _ pHead2: ListNode?) -> ListNode? {
        // write code here
        guard pHead1 != nil else { return pHead2 }
        guard pHead2 != nil else { return pHead1 }
        var p1 = pHead1
        var p2 = pHead2
        let mp: ListNode? = ListNode(val: -1)
        var temp = mp
        while p1 != nil && p2 != nil {
            if p1!.val <= p2!.val {
                temp?.next = p1
                p1 = p1?.next
            } else {
                temp?.next = p2
                p2 = p2?.next
            }
            temp = temp?.next
        }
        temp?.next = p1 == nil ? p2 : p1
        return mp?.next
    }
}


